List of papers and topics

More on classical CSPs

Despite the Bulatov-Zhuk theorem some topics remain open for finite-domain CSPs. In particular the NL-conjecture is open, see Polymorphisms and How to Use Them (https://drops.dagstuhl.de/opus/volltexte/2017/6959/pdf/DFU-Vol7-15301-1.pdf), Conjecture 50 and attached references.

Infinite-domain CSPs

For infinite-domain CSPs, one focuses on specific classes of structures A and try to obtain new algorithmic/algebraic results. One of the central concepts is that of ω-categoricity, which is a property of A that is sufficient for the complexity of CSP(A) to be characterized by Pol(A).

A theory of “smooth approximations” was developped recently to unify the existing results in infinite-domain constraint satisfaction:

Polymorphisms of ω-categorical structures can be wild. Usually, one uses some Ramsey-theoretic arguments to simply such polymorphisms. This is possible when the underlying structure (or an expansion thereof) satisfies the “Ramsey property”.

Promise CSPs

PCSPs are problems parametrized by two relational structure A,B such that there exist a homomorphism AB. The problem PCSP(A,B) takes as input X, and the goal is to decide between

There has been a lot of papers in the recent years about this topic. Small excerpt of the relevant literature:

PCSPs that are known to be in P are usually solved by one of the following methods, or a specific mixture thereof: either use the basic linear programming relaxation (BLP), or use the affine integer programming relaxation (AIP).
Algorithmic results:

Classification results (of the form “Given a specific class of PCSPs, describe the border between Ptime and NP-hard PCSPs”):